
/**
 * @Project : Clion_ProgrammingExercises
 * @File : 0494
 * @Author : WangRuoyu 
 * @Date : 2023/5/26 10:35
 */

#include <vector>
#include "iostream"

using namespace std;

class Solution {
public:
    int findTargetSumWays(vector<int> &nums, int target) {
        int sum = 0;
        for (int a: nums) {
            sum += a;
        }
        if (abs(target) > sum) {
            return 0;
        }

        int f[nums.size() + 1][2 * sum + 1];
        for (int i = 0; i <= nums.size(); ++i) {
            for (int j = 0; j <= 2 * sum; ++j) {
                f[i][j] = 0;
            }
        }

        f[0][sum] = 1;

        for (int i = 1; i <= nums.size(); ++i) {
            for (int j = 0; j <= 2 * sum; ++j) {
                if (j - nums[i - 1] >= 0 && j - nums[i - 1] <= 2 * sum) {
                    f[i][j] += f[i - 1][j - nums[i - 1]];
                }
                if (j + nums[i - 1] >= 0 && j + nums[i - 1] <= 2 * sum) {
                    f[i][j] += f[i - 1][j + nums[i - 1]];
                }
            }
        }

        return f[nums.size()][target + sum];
    }
};

// dfs + 剪枝
//class Solution {
//public:
//    vector<int> n;
//    int t;
//    int sum = 0;
//    int res = 0;
//
//    void dfs(int k, int s, int remove) {
//        if (abs(s - t) > remove) {
//            return;
//        }
//        if (k == n.size()) {
//            if (s == t) res++;
//            return;
//        }
//        dfs(k + 1, s - n[k], remove - n[k]);
//        dfs(k + 1, s + n[k], remove - n[k]);
//    }
//
//    int findTargetSumWays(vector<int> &nums, int target) {
//        n = nums;
//        t = target;
//        for (int a: nums) {
//            sum += a;
//        }
//        dfs(0, 0, sum);
//        return res;
//    }
//};

int main() {
    Solution sl;
    vector<int> nums = {1, 1, 1, 1, 1};
    int target = 3;
    printf("%d", sl.findTargetSumWays(nums, target));
    return 0;
}